package com.hy.backtracking3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class IncrementSubset {


    /**
     * 491.递增子序列
     * 力扣题目链接
     *
     * 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
     *
     * 示例:
     *
     * 输入: [4, 6, 7, 7]
     * 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
     * 说明:
     *
     * 给定数组的长度不会超过15。
     * 数组中的整数范围是 [-100,100]。
     * 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
     * 思路
     * 如果对回溯算法基础还不了解的话，我还特意录制了一期视频：带你学透回溯算法（理论篇） 可以结合题解和视频一起看，希望对大家理解回溯算法有所帮助。
     *
     * 这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。
     *
     * 这又是子集，又是去重，是不是不由自主的想起了刚刚讲过的90.子集II。
     *
     * 就是因为太像了，更要注意差别所在，要不就掉坑里了！
     *
     * 在90.子集II中我们是通过排序，再加一个标记数组来达到去重的目的。
     *
     * 而本题求自增子序列，是不能对原数组经行排序的，排完序的数组都是自增子序列了。
     *
     * 所以不能使用之前的去重逻辑！
     *
     * 本题给出的示例，还是一个有序数组 [4, 6, 7, 7]，这更容易误导大家按照排序的思路去做了。
     *
     * 为了有鲜明的对比，我用[4, 7, 6, 7]这个数组来举例，抽象为树形结构如图：
     *
     */

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();


    public List<List<Integer>> getIncrementSubset(int [] num,int startIndex){
        Arrays.sort(num);
        if (num.length == 0){
            res.add(new ArrayList<>());
        }
        incrementSubset(num,startIndex);
        return res;
    }
    public void incrementSubset(int [] num,int startIndex){
        if (path.size() > 1){
            res.add(new ArrayList<>(path));
        }

        if (startIndex >= num.length){
            return;
        }
        int [] used = new int[101];
        for (int i = startIndex; i < num.length; i++) {
            // 去重判断  num[i] < path.get(path.size() - 1)   标记去重   或者  用 map 存num[i]  标记去重
            if (!path.isEmpty() && num[i] < path.get(path.size() - 1) || (used[num[i]] == 1)){
                continue;
            }
            // 赋值 标记 已计算的数据
            used[num[i]] = 1;
            path.add(num[i]);
            // 回溯   剪枝
            incrementSubset(num,i+1);
            path.remove(path.size() - 1);
        }
    }



    public static void main(String[] args) {
        IncrementSubset incrementSubset = new IncrementSubset();
        int [] num = {4, 6, 7, 7};
        System.out.println("res: "+incrementSubset.getIncrementSubset(num,0));

    }
}
